<?php
// https://leetcode-cn->com/problems/$odd-$even-linked-list/solution/qi-ou-lian-biao-by-leetcode-solution/

// 对于原始链表，每个节点都是奇数节点或偶数节点。头节点是奇数节点，头节点的后一个节点是偶数节点，相邻节点的奇偶性不同。
// 因此可以将奇数节点和偶数节点分离成奇数链表和偶数链表，然后将偶数链表连接在奇数链表之后，合并后的链表即为结果链表。

class Solution {
    public function oddEvenList($head)
    {
        // 如果链表为空或者只有一个节点，则直接返回链表
        if ($head === null || $head->next === null) return $head;

        // 奇数节点
        $odd = $head;

        // 偶数节点
        $even = $evenHead = $head->next;

        while ($odd->next !== null && $even->next !== null) {
            // 更新奇数节点时，奇数节点的后一个节点需要指向偶数节点的后一个节点  【往后走两个节点】 1 3 5……
            $odd->next = $odd->next->next;
            $odd = $odd->next;

            // 更新偶数节点时，偶数节点的后一个节点需要指向奇数节点的后一个节点   【往后走两个节点】 2 4 6……
            $even->next = $even->next->next;
            $even = $even->next;
        }

        // 将偶数链表连接在奇数链表之后
        $odd->next = $evenHead;

        return $head;
    }
}